home *** CD-ROM | disk | FTP | other *** search
/ PC Media 22 / PC MEDIA CD22.iso / share / prog / datalib2 / index.cpp < prev    next >
C/C++ Source or Header  |  1995-08-14  |  17KB  |  540 lines
  1. #include "datapriv.hpp"
  2.  
  3. /*
  4.    This file contains the routines concerned with the generation and use
  5.    of index files
  6. */
  7.  
  8. /***************************************************************************
  9.  
  10.  Verify Index
  11.  
  12.  The following routine verifys an index by opening a record on that index
  13.  and checking that all records are present and in order
  14.  
  15.  
  16. ***************************************************************************/
  17.  
  18. long clusnrec;        // Total number of records found in clusters
  19.  
  20. int database::verifyindex(char *ind,int depth,void (*progress)(int,long),int order)
  21. {
  22.  if (!getindkey(ind)) return INVIND;    // Must be valid attached index
  23.  
  24.  record rec(*this,ind);
  25.  
  26.  char res[128],resn[128];
  27.  int rtype;
  28.  char iexp[128];
  29.  strcpy(iexp,getindkey(ind));
  30.  rec.select(FIRST,ALL);
  31.  
  32.  if (!depth) return 0;
  33.  
  34.  // Write all changed clusters to the index file
  35.  
  36.  indclus *ip=rec.curind->icp->oi->topind;
  37.  while(ip)
  38.  {
  39.   if (ip->change && ip->valid)
  40.   {
  41.    ip->change=0;
  42.    Fseek(ip->fp,ip->clusn*512L,SEEK_SET); Fwrite(ip->clusdat,1,512,ip->fp);
  43.   }
  44.   ip=ip->next;
  45.  }
  46.  
  47.  if (progress) (*progress)(1,0);
  48.  clusnrec=0;
  49.  if (!rec.curind->icp->oi->topind->verclus(progress,order)) return ERRINTREE;
  50.  if (clusnrec!=getnrec()) return INCOMP;
  51.  if (depth<2) return 0;
  52.  
  53.  rec.eval(iexp,res,rtype);
  54.  for(long i=1; i<getnrec(); i++)     // Depth=2, check out record order
  55.  {
  56.   if (progress)
  57.   {
  58.    if (i==1) (*progress)(2,i);
  59.    if (!(i%order)) (*progress)(2,i);
  60.   }
  61.   if (rec.select(NEXT,ALL)) return INCOMP;
  62.  
  63.   rec.eval(resn,rtype);
  64.   double comp;
  65.   switch(rtype)
  66.   {
  67.    case OPINT : comp=*(double *)resn-*(double *)res; break;
  68.    case OPDATE: comp=atol(resn)-atol(res);
  69.    case OPSTR : comp=strcmp(resn,res);
  70.   }
  71.   if (comp<0) return OORD;
  72.   memcpy(res,resn,100);
  73.  }
  74.  if (depth<3) return 0;
  75.  
  76.                   // Depth 3, check all records present in index
  77.  record rp(*this); rp.select(FIRST);
  78.  record frp(*this,ind);
  79.  for(i=1; i<=getnrec(); i++)
  80.  {
  81.   if (progress)
  82.   {
  83.    if (i==1) (*progress)(3,i);
  84.    if (!(i%order)) (*progress)(3,i);
  85.   }
  86.   rp.eval(getindkey(ind),res,rtype);
  87.   if (frp.selkey(res,READIND,rtype)) return RECNOTFND;
  88.   while(rp.getrecnum()!=frp.getrecnum()) frp.selkey();
  89.   rp.select(NEXT,ALL);
  90.  }
  91.  return 0;
  92. }
  93.  
  94. // Verify a cluster tree, return last key if OK, return 0 on error
  95. // If record cluster then add number of records to clusnrec
  96.  
  97. char *indclus::verclus(void (*progress)(int,long),int order)
  98. {
  99.  long nrec;        // Points to each record in index
  100.  char *lrec,*nkey;
  101.  indclus *ni;
  102.  int i,created;
  103.  
  104.  if (clustyp)    // Block cluster
  105.  {
  106.   for(i=0; i<nclusrec; i++)    // Check each cluster in the block
  107.   {
  108.    int err=0;
  109.    nrec=*(long *)(clusdat+4+i*reclen);    // Next block down
  110.    nkey=clusdat+12+i*reclen;        // Last key of next block down
  111.    ni=new indclus(nrec,0,oi);        // Next index down
  112.    lrec=ni->verclus(progress,order);
  113.    if (!lrec) err=1;             // Error in next block down
  114.    else
  115.     switch(oi->restype)            // Check last key in child matches this
  116.     {
  117.      case OPSTR : if (strncmp(nkey,lrec,explen)) err=1; break;
  118.      case OPINT : if (*(double *)nkey-*(double *)lrec) err=1; break;
  119.      case OPDATE : if (strncmp(nkey,lrec,8)) err=1; break;
  120.     }
  121.    delete ni;
  122.    if (err) return 0;
  123.   }
  124.  }
  125.  else        // Record cluster
  126.  {
  127.   long oclus=clusnrec;
  128.   clusnrec+=nclusrec;
  129.   if (progress && (oclus/order!=clusnrec/order)) (*progress)(1,clusnrec);
  130.  }
  131.  char *rv=(clusdat+12+reclen*(nclusrec-1));
  132.  return rv;
  133. }
  134.  
  135.  
  136. /***************************************************************************
  137.  
  138.  BUILD INDEX
  139.  
  140.  The following routines and structures are concerned with building an
  141.  index from scratch. A flat file of unsorted record clusters is built,
  142.  these are then sorted, and then the tree is built at the end of the file
  143.  finally the header record is written
  144.  
  145. ***************************************************************************/
  146.  
  147. // The following holds a disk buffer, there are DBUF of these.
  148.  
  149. #define DBUF    5    // Number of disk clusters buffered in indexes
  150.  
  151. struct _dbuf
  152. {
  153.  char buf[512];        // Holds the data from disk
  154.  char uflag;        // Counter increments once for every use
  155.  long dpos;        // Position in disk file
  156.  int cval;        // contents have changed if cval==1
  157. };
  158.  
  159. _dbuf *_dbp;    // Points to disk buffer array
  160.  
  161.  
  162. /************** Build Index ... This routine builds an index ************/
  163.  
  164. // Returns 0 on success, error otherwise
  165.  
  166. int database::buildindex(char *expr,char *fname,void (*progress)(int,long),int order)
  167. {
  168.  record rec(*this,NOIND);    // record
  169.  int indlen,indtype;        // Index length and type
  170.  int tindlen;            // total index length with pad
  171.  char ws[128],*wsp;        // Work space, generic pointer
  172.  FILE *ifp;            // Index file pointer
  173.  int ipad;            // No. of characters to pad out index result
  174.  int nclusrec;            // No. of records/cluster
  175.  char buf[512];            // Useful buffer
  176.  long i,j,k;
  177.  int dum;
  178.  long topclus=1;        // Cluster at top of tree
  179.  
  180.  int rv=0;
  181.  if (nrec) rv=rec.select(FIRST,ALL);
  182.  if (!(indlen=rec.indchk(expr,indtype)) || rv) return EXPRERR;
  183.  ipad=(4-indlen%4)%4;
  184.  tindlen=indlen+ipad;
  185.  nclusrec=504/(indlen+ipad+8);
  186.  
  187.  strcpy(ws,fname);
  188.  if (wsp=strchr(ws,'.')) *wsp=0;
  189.  strcat(ws,".NDX");
  190.  if (!(ifp=fopen(ws,"w+b"))) return NOINDEX;
  191.  
  192.  Fwrite(buf,512,1,ifp);        // Write a blank header (fill it in later)
  193.  rec.eval(expr,ws,dum);        // Tokenise expression
  194.  
  195.  if (nrec)
  196.  {
  197.   long nwrit=0;
  198.   while(!rv)            // Write out all records & index expressions
  199.   {
  200.    long nwr=0;            // No. of records written
  201.    int dum;
  202.    char *ip=buf+4;        // Pointer to next free space in buffer
  203.  
  204.    for(i=0; i<nclusrec; i++)
  205.    {
  206.     if (rv) break;
  207.     if (!rec.eval(ws,dum)) {fclose(ifp); return EXPRERR;}
  208.     *(long *)ip=0; ip+=4; *(long *)ip=rec.getrecnum(); ip+=4;    // rec. no.
  209.     switch(indtype)                        // Result
  210.     {
  211.      case OPINT : *(double *)ip=*(double *)ws; ip+=sizeof(double); break;
  212.      case OPSTR : wsp=ws; while(*wsp++); wsp--; k=wsp-ws;
  213.           for(j=0; j<tindlen-k; j++) *wsp++=' ';
  214.           strncpy(ip,ws,tindlen); ip+=tindlen;
  215.           break;
  216.      case OPDATE : strncpy(ip,ws,8); ip+=tindlen;  break;
  217.     }
  218.     nwr++; nwrit++;
  219.     if (progress && (nwrit==1 || !(nwrit%order))) (*progress)(1,nwrit);
  220.     rv=rec.select(NEXT,ALL);
  221.    }
  222.    *(double *)ip=0;
  223.    *(long *)buf=(long)nwr;
  224.    Fwrite(buf,512,1,ifp);
  225.   }
  226.  
  227.   _dbp=new _dbuf[DBUF];
  228.   indsort(ifp,indtype,tindlen+8,indlen,nrec,nclusrec,progress,order);
  229.   delete _dbp;
  230.   if (progress) (*progress)(3,1);
  231.   buildtree(ifp,tindlen+8,indlen,nclusrec,nrec/nclusrec+1,topclus);
  232.  }
  233.  
  234.  Fseek(ifp,0L,SEEK_SET);    // Now write header
  235.  memset(buf,0,512);
  236.  *(long *)buf=topclus; *(long *)(buf+4)=topclus+1;
  237.  switch(indtype)
  238.  {
  239.   case OPINT : buf[9]='N'; buf[16]=1; break;
  240.   case OPDATE: buf[9]='D'; buf[16]=0; break;
  241.   case OPSTR : buf[9]='C'; break;
  242.  }
  243.  buf[12]=indlen;
  244.  buf[14]=nclusrec;
  245.  buf[18]=indlen+ipad+8;
  246.  strcpy(buf+24,expr);
  247.  Fwrite(buf,512,1,ifp);
  248.  if (!nrec) {memset(buf,0,512); Fwrite(buf,512,1,ifp);}
  249.  fclose(ifp);
  250.  return 0;
  251. }
  252.  
  253. /********** Index sort ******************************************************/
  254.  
  255. // These functions implement a full index sort on the unsorted index
  256. // file. 
  257.  
  258. // The following structure is a buffer which holds a cluster from
  259. // the index file, whenever 2 elements are compared or sorted, the
  260. // buffers are checked first to see if the elements are contained therein
  261.  
  262. struct _ibf
  263. {
  264.  char *buf;        // Points to character data
  265.  _dbuf *dbuf;        // Points to disk buffer associated with index
  266.  long low;        // Lowest element number in buffer
  267.  long up;        // Highest element number in buffer
  268.  long n;        // Element number in buffer to examine
  269.  char *an;        // Address of element number in buffer to examine
  270.  char *tn;        // Points to element data
  271.  long dpos;        // Position in disk file
  272.  FILE *fp;        // File pointer to index file
  273.  int nclusrec;        // No. of records/cluster
  274.  int indlen;        // index length
  275.  int indexplen;        // index expression length
  276.  int indtype;        // Index type
  277.  
  278.  
  279.  _ibf(FILE *,int,int,int,int);
  280.             // Constructor initialises buffer
  281.  ~_ibf();        // Destructor flushes buffer to disk
  282.  void setn(long n);    // Set element no. of buffer to n
  283.             // This will check if n is in the buffer
  284.                         // and if it is not will save the buffer
  285.                         // and update the buffer with new value
  286.  
  287.  void indswap(struct _ibf &s);        // Swap element with s
  288.  int  indcomp(struct _ibf &s);        // Compare element with s
  289.  
  290. };
  291.  
  292. _ibf::_ibf(FILE *ifp,int inclusrec,int iindlen,int iindexplen,
  293.                  int iindtype)
  294. {
  295.  fp=ifp;
  296.  nclusrec=inclusrec;
  297.  indlen=iindlen;
  298.  indexplen=iindexplen;
  299.  indtype=iindtype;
  300.  up=-1;            // Flag dbuf is invalid
  301.  dbuf=0;
  302. }
  303.  
  304. _ibf::~_ibf()
  305. {
  306.  dbuf->uflag--;
  307.  if (!(dbuf->uflag) && dbuf->cval)
  308.  {
  309.   Fseek(fp,512L*dpos,SEEK_SET); Fwrite(buf,512,1,fp);
  310.  }
  311. }
  312.  
  313. // Set element number in buffer
  314. // If we are simply changing to another element in the same buffer then
  315. // just move the pointers. If we are moving buffers then check if the
  316. // current buffer should be written back to disk, see if anyone else
  317. // is using the new buffer & if so grab it, if not then set up a new
  318. // buffer holding the cluster we require from disk.
  319.  
  320. void _ibf::setn(long nw)
  321. {
  322.  n=nw;
  323.  if (nw<low || nw>up)        // Update buffer ?
  324.  {
  325.   if (dbuf)        // Only if dbuf is valid
  326.   {
  327.    dbuf->uflag--;
  328.    if (dbuf->cval && !dbuf->uflag) 
  329.    {
  330.     Fseek(fp,512L*dpos,SEEK_SET); Fwrite(buf,512,1,fp);
  331.    }
  332.   }
  333.  
  334.   dpos=n/nclusrec+1;
  335.   
  336.   int fflag=0;            // Flags buffer already exists
  337.   _dbuf *nfree;            // Points to a free buffer
  338.  
  339.   for(int i=0; i<DBUF; i++)    // Now do we already have this buffer ?
  340.   {
  341.    if (_dbp[i].dpos==dpos) {fflag=1; break;}
  342.    if (!(_dbp[i].uflag)) nfree=&(_dbp[i]);
  343.   }
  344.   if (fflag)    // Someone else has grabbed this buffer for us
  345.   {
  346.    dbuf=&(_dbp[i]); buf=dbuf->buf; dbuf->uflag++;
  347.   }
  348.   else        // We'll grab a new buffer
  349.   {
  350.    nfree->uflag=1; nfree->dpos=dpos; nfree->cval=0; buf=nfree->buf;
  351.    Fseek(fp,512L*dpos,SEEK_SET); Fread(buf,512,1,fp);
  352.    dbuf=nfree;
  353.   }
  354.   low=(dpos-1)*nclusrec;
  355.   up=dpos*nclusrec-1;
  356.  }
  357.  an=buf+4+(n-low)*indlen; tn=an+8;
  358. }
  359.  
  360. // This function swaps the current element with the current element of s
  361.  
  362. void _ibf::indswap(_ibf &s)
  363. {
  364.  char temp[110];
  365.  
  366.  memcpy(temp,an,indlen);
  367.  memcpy(an,s.an,indlen);
  368.  memcpy(s.an,temp,indlen);
  369.  dbuf->cval=1; s.dbuf->cval=1;        // Show contents have changed
  370. }
  371.  
  372. // This function compares the current element with the current element of s
  373.  
  374. int _ibf::indcomp(_ibf &s)
  375. {
  376. // if (indtype==OPSTR) return(strncmp(tn,s.tn,indexplen));
  377.  if (indtype!=OPINT) return(strncmp(tn,s.tn,indexplen));
  378.  
  379.  double dr=(*(double *)(tn))-(*(double *)(s.tn));
  380.  
  381.  if (dr>0) return 1;
  382.  if (dr<0) return -1;
  383.  return 0;
  384. }
  385.  
  386. // The following function takes a pointer to an index file, and 
  387. // sorts the elements in it, it is a quicksort derived from the Zortech
  388. // qsort function itself derived from the Ray Gardner public domain function
  389.  
  390. // indtype is the type of result, indlen the length of index+pad+pointers,
  391. // indexplen is the length of index expression alone, nel is the no. of
  392. // elements, and nclusrec the number of records/cluster
  393.  
  394. void database::indsort(FILE *ifp,int indtype,int indlen,int indexplen,
  395.                long nel,int nclusrec,void (*progress)(int,long),int order)
  396. {
  397.  long nswap=0;
  398.  long lastorder=-1;
  399.  long stack[40],*sp;                          // stack and stack pointer
  400.  _ibf i(ifp,nclusrec,indlen,indexplen,indtype);   // scan and limit pointers
  401.  _ibf j(ifp,nclusrec,indlen,indexplen,indtype);
  402.  _ibf limit(ifp,nclusrec,indlen,indexplen,indtype);
  403.  _ibf base(ifp,nclusrec,indlen,indexplen,indtype);
  404.  _ibf temp(ifp,nclusrec,indlen,indexplen,indtype);
  405.  for(int x=0; x<DBUF; x++) {_dbp[x].dpos=-1; _dbp[x].uflag=0;} // Init buffers
  406.  
  407.  sp=stack;                              // Init stack pointer
  408.  base.setn(0);
  409.  limit.setn(nel);                 /* pointer past end of array      */
  410.  while (1)                              /* repeat until done then return  */
  411.  {
  412.   if (nswap>lastorder && progress)
  413.      {(*progress)(2,nswap); lastorder=nswap+order;}
  414.  
  415.   while (limit.n-base.n>5)    // Max span=5, otherwise insertion sort
  416.   {
  417.    temp.setn(((unsigned long)(limit.n-base.n)>>1)+base.n);  // swap middle, base
  418.    temp.indswap(base); nswap++;
  419.  
  420.    i.setn(base.n+1);                   /* i scans from left to right     */
  421.    j.setn(limit.n-1);                   /* j scans from right to left     */
  422.  
  423.    if (i.indcomp(j)>0) {i.indswap(j); nswap++;}       // Sedgewick's
  424.                               //    three-element sort
  425.    if (base.indcomp(j)>0) {base.indswap(j); nswap++;} //     sets things up
  426.                               //       so that
  427.    if (i.indcomp(base)>0) {i.indswap(base); nswap++;} //         i <= base <= j
  428.                               // base is the pivot element
  429.  
  430.    while (1)
  431.    {
  432.     do i.setn(i.n+1);              /* move i right until i >= pivot */
  433.     while (i.indcomp(base)<0);
  434.  
  435.     do j.setn(j.n-1);                 /* move j left until j <= pivot  */
  436.     while (j.indcomp(base)>0);
  437.  
  438.     if (i.n>j.n) break;               /* break loop if pointers crossed */
  439.  
  440.     i.indswap(j);                  /* else swap elements, keep scanning */
  441.     nswap++;
  442.    }
  443.  
  444.    nswap++;
  445.    base.indswap(j);                   /* move pivot into correct place  */
  446.    if (j.n-base.n>limit.n-i.n)         /* if left subfile is larger...   */
  447.    {
  448.     sp[0]=base.n; sp[1]=j.n;          /* stack left subfile base        */
  449.     base.setn(i.n);                   /*    and limit                   */
  450.    }                                  /* sort the right subfile         */
  451.  
  452.    else                               /* else right subfile is larger   */
  453.    {
  454.     sp[0]=i.n; sp[1]=limit.n;         /* stack right subfile base       */
  455.     limit.setn(j.n);                  /*    and limit                   */
  456.    }                                  /* sort the left subfile          */
  457.  
  458.    sp+=2;                          /* increment stack pointer        */
  459.   }
  460.  
  461.   // Insertion sort on remaining subfile
  462.  
  463.   i.setn(base.n+1);
  464.   while (i.n<limit.n)
  465.   {
  466.    j.setn(i.n);
  467.    temp.setn(j.n-1);
  468.    while (j.n>base.n && temp.indcomp(j)>0)
  469.    {
  470.     temp.indswap(j); nswap++;
  471.     j.setn(j.n-1);
  472.     temp.setn(j.n-1);
  473.    }
  474.    i.setn(i.n+1);
  475.   }
  476.  
  477.   if (sp>stack)       /* if any entries on stack...     */
  478.   {
  479.    sp-=2;             /* pop the base and limit         */
  480.    base.setn(sp[0]);
  481.    limit.setn(sp[1]);
  482.   }
  483.   else break;         /* else stack empty, all done     */
  484.  }
  485. }
  486.  
  487. // This routine builds an index tree in a sorted flat index file
  488. // indlen is length of index + pointers
  489. // nrec is no. of records
  490. // nclusrec is no. of records/cluster
  491. // nclus is no. of clusters at the level of tree being indexed
  492. // indexplen is the index expression length
  493. // topclus is returned as the top cluster in the tree
  494.  
  495. void database::buildtree(FILE *fp,int indlen,int indexplen,
  496.              int nclusrec,long nclus,long &topclus)
  497. {
  498.  long fclus=1;            // First cluster of this level of tree
  499.  long flclus;            // First cluster of level being written
  500.  char buf[512],ibuf[512];    // Holds current cluster & cluster from disk
  501.  int recclus=1;            // Flags we are looking at a record cluster
  502.  
  503.  if (nclus==1) flclus=1;
  504.  while(nclus>1)
  505.  {
  506.   long tlclus=0;        // Totals clusters written at this level
  507.   long nclev=nclus/nclusrec;    // No. of clusters to write at this level
  508.  
  509.   Fseek(fp,0L,SEEK_END);
  510.   flclus=ftell(fp)/512L;    // First cluster at this level
  511.  
  512.   for(long i=0; i<=nclev; i++)    // For each cluster at this level
  513.   {
  514.    Fseek(fp,fclus*512L,SEEK_SET);    // Find first cluster to be examined
  515.    char *cop=buf+4;            // Location to copy record to
  516.    int nrecclus=0;            // No. of records in cluster
  517.  
  518.    for(int j=0; j<nclusrec; j++)
  519.    {
  520.     char *lr;                // points to last record in cluster
  521.  
  522.     if (!(nclus--)) break;            // Last cluster yet ?
  523.     Fread(ibuf,512,1,fp);            // Cluster to be examined
  524.     lr=ibuf+4+(*(long *)ibuf-recclus)*indlen;    // Last record in cluster
  525.     *(long *)cop=fclus++; cop+=sizeof(long);    // Record number
  526.     *(long *)cop=0; cop+=sizeof(long);
  527.     memcpy(cop,lr+8,indexplen);            // Copy in last record
  528.     cop+=indlen-8;
  529.     nrecclus++;
  530.    }
  531.    tlclus++;
  532.    *(long *)buf=nrecclus-1;            // No. of records in cluster
  533.    Fseek(fp,0L,SEEK_END); Fwrite(buf,512,1,fp);    // move to file end & write
  534.   }
  535.   fclus=flclus; nclus=tlclus;             // Now index level just done
  536.   if (recclus) recclus=0;            // Now looking at blocks
  537.  }
  538.  topclus=flclus;                // Top cluster in tree
  539. }
  540.